/*
    编写一个高效算法来搜索m x n矩阵matrix 中的一个目标值target，该矩阵具有以下特性：
    *每列的元素从左到有升序排列
    *每列的元素从上到下升序排列
    示例：
    有矩阵如下：
     [
        [ 1, 4, 7,11,15],
        [ 2, 5, 8,12,19],
        [ 3, 6, 9,16,22],
        [10,13,14,17,24],
        [18,21,23,26,30]
    ]
    给定target = 5,返回true，
    给定target = 20,返回false
*/

let matrix = [
    [ 1, 4, 7,11,15],
    [ 2, 5, 8,12,19],
    [ 3, 6, 9,16,22],
    [10,13,14,17,24],
    [18,21,23,26,30]
]

const result = search(matrix, 17)
console.log(result)

function search(matrix, target, leftIndex, rightIndex){
    if(leftIndex == null) leftIndex = 0
    if(rightIndex == null) rightIndex = matrix.length - 1
    if(leftIndex>rightIndex)
        return false
    const midIndex = Math.floor((leftIndex+rightIndex)/2)
    const midRow = matrix[midIndex]
    const min = midRow[0]
    const max = midRow[midRow.length-1]
    if(target == min || target == max)
        return true
    if(target < min)
        return search(matrix, target, leftIndex, midIndex - 1) //只向上找
    if(target > max)
        return search(matrix, target, midIndex + 1, rightIndex) //只向下找
    return binarySearch(midRow, target) 
        || search(matrix, target, leftIndex, midIndex - 1)
        || search(matrix, target, midIndex + 1, rightIndex)
}

//二分查找
function binarySearch(row, n, leftIndex, rightIndex){
    if(leftIndex == null) leftIndex = 0
    if(rightIndex == null) rightIndex = row.length - 1
    if(leftIndex>rightIndex)
        return false
    const midIndex = Math.floor((leftIndex+rightIndex)/2)
    const mid = row[midIndex]
    if(mid == n)
        return true
    if(mid < n)
        return binarySearch(row, n,  midIndex + 1, rightIndex)
    //mid > n
    return binarySearch(row, n,  leftIndex, midIndex-1)
}